//
// Created by 要江川 on 2023/7/22.
//
#include<iostream>

using namespace std;

#include "vector"

class Solution
{
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch1(vector<int> &nums, int target)//左闭右闭区间
    {
        int l = 0, r = nums.size() - 1, middle;
        while (l <= r) {
            middle = (l + r) / 2;
            if (target < nums[middle]) {
                r = middle - 1;
            } else if (target > nums[middle]) {
                l = middle + 1;
            } else return middle;
        }
        return -1;
    }

    int binarySearch2(vector<int> &nums, int target)//区间左闭右开
    {
        int l = 0, r = nums.size() , middle;//注意这里的r没有减一
        while (l < r) {
            middle = (l + r) / 2;
            if (target < nums[middle]) {
                r = middle ;//右开，在if判断时就确定了target不在区间内，所以不用减一
            } else if (target > nums[middle]) {
                l = middle + 1;
            } else return middle;
        }
        return -1;
    }

    int binarySearch(vector<int> &nums, int target)//改进写法，找到第一个出现的位置
    {
        int l = 0, r = nums.size() - 1, middle;
        while (l <= r) {
            middle = (l + r) / 2;
            if (target <= nums[middle]) {//相等时也继续向左寻找，找到最左边的
                r = middle - 1;
            } else {
                l = middle + 1;
            }
        }
        if(nums[l]==target) return l;
        return -1;
    }
};

void test()
{
    int arr[4] = {1, 1, 1, 5};
    vector<int> nums(arr, arr + 4);
    Solution s;
    cout << s.binarySearch(nums, 7);
}

int main()
{
    test();
}
